package main

/**
 * @Author: DengLibin
 * @Date: Create in 2023-01-12 10:15:31
 * @Description:
 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
 输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
*/

//时间复杂度O(n) 空间复杂度O(n)
func missingNumber(nums []int) int {
	l := len(nums)
	arr := make([]bool, l+1)
	for _, num := range nums {
		arr[num] = true
	}
	for i, a := range arr {
		if !a {
			return i
		}
	}
	return 0
}

//数学方法 时间复杂度O(n) 空间复杂度O(1)
//将从 0 到 n 的全部整数之和记为 total
//将数组 nums元素之和记为 arrSum，则 arrSum 比 total少了丢失的一个数字
func missingNumber2(nums []int) int {
	l := len(nums) //0 - l
	//数列求和
	total := l * (l + 1) / 2

	sum := 0
	for _, num := range nums {
		sum += num
	}
	return total - sum
}
